/*
Clone Graph
Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.


OJ's undirected graph serialization:
Nodes are labeled uniquely.

We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.
As an example, consider the serialized graph {0,1,2#1,2#2,2}.

The graph has a total of three nodes, and therefore contains three parts as separated by #.

First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
Second node is labeled as 1. Connect node 1 to node 2.
Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.
Visually, the graph looks like the following:

1
/ \
/   \
0 --- 2
/ \
\_/
*/

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <string>
#include <stack>
#include <queue>
#include <fstream>
#include <sstream>
#include <unordered_set>
#include "print.h"
using namespace std;

/**
* Definition for binary tree*/


void testForStack()
{
	stack<int> mystack;
	mystack.push(10);
	mystack.push(20);
	mystack.top() -= 5;
	cout << "mystack.top() is now " << mystack.top() << endl;
}

void testForIntToString()
{
	int a = 10;
	stringstream ss;
	ss << a;
	string str = ss.str();
	cout << str << endl;

	string str1 = to_string(a);

}



class Solution {
public:
	
	UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
		if (node == NULL)
		{
			return node;
		}

		UndirectedGraphNode *result = new UndirectedGraphNode(node->label);
		map<UndirectedGraphNode*, UndirectedGraphNode*> mapGraph;
		queue<UndirectedGraphNode*> queueGraph;
		
		queueGraph.push(node);
		mapGraph.insert(make_pair(node, result));

		while (!queueGraph.empty())
		{
			UndirectedGraphNode* cur = queueGraph.front();
			queueGraph.pop();

			for (int i = 0; i < cur->neighbors.size(); i++)
			{
				UndirectedGraphNode *neighPtr = cur->neighbors[i];
				if (mapGraph.find(neighPtr)==mapGraph.end())
				{
					UndirectedGraphNode *newNeigh = new UndirectedGraphNode(neighPtr->label);
					mapGraph[cur]->neighbors.push_back(newNeigh);
					mapGraph[neighPtr] = newNeigh;
					queueGraph.push(neighPtr);
				}
				else
				{
					mapGraph[cur]->neighbors.push_back(mapGraph[neighPtr]);
				}
			}

		}


		return result;


	}
};





int main(int argc, char* argv[])
{



	string start = "hit";
	string end = "cog";


	//cout << "Input the string" << endl;
	//string str;

	//cin >> str;

	string str = "aab";





	vector<vector<string>> result;



	Solution s;
	result = s.partition(str);
	//stackTree.push(p->left);
	//stackTree.push(p->right);
	//if (s.isPalindrome(str1))
	//	cout << " True" << endl;
	//else
	//	cout << "false" << endl;
	system("pause");
	return 0;
}
//std::unordered_set<std::string> myset =
//{ "hot", "dot", "dog", "lot", "log" };

//std::cout << "myset contains:";
// for (auto it = myset.begin(); it != myset.end(); ++it)
//std::cout << " " << *it;
//;; std::cout << std::endl;

//TreeNode *root = new TreeNode(1);
//TreeNode *left = new TreeNode(2);
//TreeNode *right = new TreeNode(3);

//root->left = left;
//root->right = right;